home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 289_01 / protect.c < prev    next >
Text File  |  1989-05-23  |  14KB  |  429 lines
  1. /*-----------------------------------------------------------------------------
  2. Update board
  3.  
  4. Revision History
  5. ----------------
  6. Gary Culp   3-14 Dec 1988  Initial version.
  7. Gary Culp   19 Dec 1988    Added prot_check_flag to handle_changed_pieces, so
  8.                            that the display routines can use it, too.
  9. -----------------------------------------------------------------------------*/
  10.  
  11. /*
  12. Glossary terms:        ***!!!
  13.    permanent  (piece)
  14.    axis
  15.    hostile    (piece or color)
  16.    friendly   (piece or color)
  17.    off-board  (piece or color)
  18.  
  19. A common piece of advice to Othello players is to take the corners of the
  20. board, because they can never be captured from you.  Not only can you depend
  21. upon their contributing to your final count of pieces, they make a good
  22. solid foundation upon which to build.  Something I haven't heard pointed out
  23. though, is that corners aren't the only pieces that can't be captured.
  24. I call any piece that can't be captured a permanent piece.  My strategy when
  25. playing Othello is to acquire as many permanent pieces as I can; and that is
  26. the strategy implemented in this game.  The most challenging part of this
  27. project, for me, was figuring out an efficient algorithm for determining which
  28. pieces in a given board configuration are permanent.  The answer was obvious
  29. (after several hours of intense thought :) ).
  30. This file contains the code which implements the algorithm.
  31.  
  32. To capture a piece (or line of pieces), P, the opponent must place 
  33. his pieces, O, on opposite sides of P.
  34. There are 4 axes through which this may be done:
  35.  
  36. horizontal   vertical   forward    backward
  37.                         diagonal   diagonal
  38.                O             O      O
  39.  O P O         P           P          P
  40.                O         O              O
  41.  
  42. If a piece is protected from being captured along all 4 axes, it cannot be
  43. captured at all, and is therefore permanent.
  44.  
  45. A piece is protected along an axis if one of these conditions is true:
  46.  
  47. 1)  The axis is full.
  48. 2)  One of the adjacent pieces along the axis is a friendly permanent piece.
  49. 3)  Both of the adjacent pieces along the axis are permanent.  (It doesn't
  50.     matter what colors they are.)
  51.  
  52. For these rules for protection along an axis to work, we have imaginary
  53. squares which lie off the edge of the board (that's why the boards are
  54. manipulated as 10x10 instead of 8x8).  These imaginary squares contain
  55. permanent pieces of a third color: "off-board".  Off-board is considered
  56. to be a friendly color, for both players.  It may seem weird to add all
  57. this imaginary stuff to the game, but it greatly simplifies handling the
  58. edge of the board.  Off-board pieces make the code simpler, smaller,
  59. and faster, at the expense of making the board data structure larger.
  60.  
  61. When to check protection and permanence:
  62.  
  63.    When a piece is played or its color is changed, all 4 of its axes must be
  64.    checked for protection (previous protection may be invalidated by color
  65.    change).
  66.  
  67.    When a protection bit that was clear is set, the piece must be checked
  68.    for permanence.
  69.  
  70.    When a piece becomes permanent, the pieces adjacent to it must be checked
  71.    for protection along the axis containing the newly permanent piece.
  72. */
  73.  
  74.  
  75. #include "othello.h"
  76.  
  77.  
  78. /* These definitions aren't used anywhere else.  They are part of a trick
  79.    for determining whether the protected axis rules are satisfied. (The
  80.    rules which deal with adjacent pieces being permanent, not the rule
  81.    about a full axis.)
  82.    Note that TRICK_PROTECTED == TRICK_ADJ1_PERM | TRICK_ADJ2_PERM.
  83. */
  84. #define TRICK_ADJ1_PERM    1 
  85. #define TRICK_ADJ2_PERM    2
  86. #define TRICK_PROTECTED    3
  87.  
  88. /*--------------------------------*/
  89. /*          Prototypes            */
  90. /*--------------------------------*/
  91.  
  92. void handle_changed_pieces(
  93.    struct board_struct *board_ptr,
  94.    int *affected_list,
  95.    int num_affected,
  96.    unsigned char new_color,
  97.    int prot_check_flag);
  98.  
  99. void new_piece_axis_fill_check(
  100.    struct board_struct *board_ptr,
  101.    int *affected_list);
  102.  
  103. void perform_all_protection_checks(struct board_struct *board_ptr);
  104.  
  105. unsigned char is_filled_axis(unsigned char *new_piece_ptr, int axis_num);
  106.  
  107. void request_prot_check(
  108.    struct board_struct *board_ptr, /* pointer to board structure */
  109.    unsigned char *cell_ptr,        /* pointer to cell */
  110.    unsigned char requested_axes);  /* requesting prot check for these axes */
  111.  
  112. int next_check(int *row_num_ptr, int *clm_num_ptr, int *axis_num_ptr);
  113.  
  114. /*--------------------------------*/
  115. /*             Variables          */
  116. /*--------------------------------*/
  117.  
  118. /* To convert axis flags to axis numbers, shift the axis flag right 4 bits;
  119.    use the result as an index into this table.
  120. */
  121. static const unsigned char bit_priority_encode[] = {
  122.    0, /* [0000] */ /* actually, no bit set */
  123.    0, /* [0001] */
  124.    1, /* [0010] */
  125.    1, /* [0011] */
  126.    2, /* [0100] */
  127.    2, /* [0101] */
  128.    2, /* [0110] */
  129.    2, /* [0111] */
  130.    3, /* [1000] */
  131.    3, /* [1001] */
  132.    3, /* [1010] */
  133.    3, /* [1011] */
  134.    3, /* [1100] */
  135.    3, /* [1101] */
  136.    3, /* [1110] */
  137.    3, /* [1111] */
  138. };
  139.  
  140. /*
  141.    For movement along an axis within a board, add or subtract
  142.    delta_array[axis_number] to a pointer to a cell within the board.
  143. */
  144. const int delta_array[4] = {11, 9, 1, 10};
  145.  
  146. static unsigned char schedule_map[10][10];
  147.  
  148.  
  149. /*------------------------------*/
  150. /*           Functions          */
  151. /*------------------------------*/
  152.  
  153.  
  154. /*
  155. Given a list of affected pieces, starting with the new piece,
  156. update the board, including the protection flags.
  157. */
  158. void
  159. update_protection_for_board(
  160.    struct board_struct *board_ptr,
  161.    int *affected_list, /* list of affected pieces, beginning with new piece */
  162.    int num_affected,   /* number of pieces in affected list */
  163.    unsigned char new_color)   /* new color for affected pieces */
  164. {
  165.    handle_changed_pieces(board_ptr, affected_list, num_affected, new_color, 1);
  166.    new_piece_axis_fill_check(board_ptr, affected_list);
  167.    perform_all_protection_checks(board_ptr);
  168. }
  169.  
  170. /*
  171. Update board according to list of pieces changed by this move (including
  172. new piece).
  173. */
  174. void
  175. handle_changed_pieces(
  176.    struct board_struct *board_ptr,
  177.    register int *affected_list, /* list of affected pieces, beginning with new piece */
  178.    int num_affected,            /* number of pieces in affected list */
  179.    unsigned char new_color,     /* new color for affected pieces */
  180.    int prot_check_flag)         /* flag: request protection checks iff set */
  181. {
  182.    register unsigned char *cell_ptr;
  183.  
  184.    /* for all pieces changed by the move, including the new piece */
  185.    while (num_affected--) {
  186.  
  187.       /* Clear all protection bits for this piece & set its new color. */
  188.       *(cell_ptr = &board_ptr->board[0][0] + *affected_list++) = new_color;
  189.  
  190.       /* Request that this piece be checked for protection along all 4 axes. */
  191.       if (prot_check_flag) {
  192.          request_prot_check(board_ptr, cell_ptr, BD_AX | FD_AX | H_AX | V_AX);
  193.       }
  194.    }
  195. }
  196.  
  197. /*
  198. Check each axis of new piece to see if we filled the axis.
  199. */
  200. void
  201. new_piece_axis_fill_check(
  202.    struct board_struct *board_ptr,
  203.    int *affected_list) /* list of affected pieces, beginning with new piece */
  204. {
  205.    unsigned char axis_flag;
  206.    unsigned char *new_piece_ptr;
  207.    register unsigned char *cell_ptr;
  208.    int axis_num;
  209.  
  210.    new_piece_ptr = &board_ptr->board[0][0] + *affected_list;
  211.  
  212.    /* for all 4 axes through the new piece */
  213.    for (axis_num = BD_NDX; axis_num <= V_NDX; axis_num++) {
  214.       if (is_filled_axis(new_piece_ptr, axis_num)) {
  215.  
  216.          /* Set full-axis bit for this axis */
  217.          SET_FA_BIT(board_ptr->fa_bits,
  218.           fa_tabl[*affected_list / 10 - 1][*affected_list % 10 - 1][axis_num]);
  219.  
  220.          /* Request protection check for each piece along this axis.
  221.             (The pieces are protected along this axis, of course.
  222.             But it's easier to keep the protection checking in one place,
  223.             so we go through the scheduler.)
  224.  
  225.             The loop which does this (below) never hits